home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Tree / N_Tree.C < prev    next >
C/C++ Source or Header  |  1992-05-15  |  12KB  |  337 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13. #include <cool/N_Tree.h>
  14.  
  15. // CoolN_Tree -- Simple constructor that sets the root to the node provided
  16. // Input:    Pointer to node object or NULL.
  17. // Output:   CoolN_Tree object created with root initialized
  18.  
  19. template <class Node, class Type, int nchild> 
  20. CoolN_Tree<Node,Type,nchild>::CoolN_Tree<Node,Type,nchild> (Node<Type,nchild>* n) {
  21.   this->root = n;                // Point root to node
  22.   this->t_mode = INORDER;            // Default traversal mode
  23.   if (n)
  24.     this->number_nodes = 1;            // Update node count
  25.   else
  26.     this->number_nodes = 0;
  27. }
  28.  
  29. // CoolN_Tree -- Simple constructor that sets the root to the node provided
  30. // Input:    Reference to node object
  31. // Output:   CoolN_Tree object created with root initialized
  32.  
  33. template <class Node, class Type, int nchild> 
  34. CoolN_Tree<Node,Type,nchild>::CoolN_Tree<Node,Type,nchild> (Node<Type,nchild>& n) {
  35.   this->root = &n;                // Point root to node
  36.   this->t_mode = INORDER;            // Default traversal mode
  37.   this->number_nodes = 1;            // Update node count
  38. }
  39.  
  40.  
  41. // CoolN_Tree -- Copy constructor makes deep copy of all nodes
  42. // Input:    Reference to CoolN_Tree object
  43. // Output:   CoolN_Tree object duplicated
  44.  
  45. template <class Node, class Type, int nchild> 
  46. CoolN_Tree<Node,Type,nchild>::CoolN_Tree<Node,Type,nchild> (const CoolN_Tree<Node,Type,nchild>& nt) 
  47. {
  48.   this->root = copy_nodes(nt.root);        // Deep copy of all nodes
  49.   this->t_mode = nt.t_mode;            // Copy traversal mode
  50.   this->number_nodes = nt.number_nodes;        // Copy node count
  51.   this->state = nt.state;            // Copy state or curpos
  52. }
  53.  
  54.  
  55. // ~CoolN_Tree -- destructor (not inline because it's virtual)
  56. // Input:    none
  57. // Output:   none
  58.  
  59. template <class Node, class Type, int nchild>
  60. CoolN_Tree<Node,Type,nchild>::~CoolN_Tree<Node,Type,nchild> () {
  61.   delete this->root;                // Delete all nodes
  62. }
  63.  
  64. // clear -- removes root and all subtrees
  65. // input -- none
  66. // output -- none
  67.  
  68. template <class Node, class Type, int nchild> 
  69. void CoolN_Tree<Node,Type,nchild>::clear () {
  70.   delete this->root;                // Delete all nodes
  71.   this->root = NULL;
  72.   this->number_nodes = 0;
  73.   this->reset();
  74. }
  75.  
  76.  
  77.  
  78. // prev -- Move position to previous node in tree. If no more nodes
  79. //         return FALSE 
  80. // Input:  None
  81. // Output: TRUE/FALSE
  82.  
  83. template <class Node, class Type, int nchild> 
  84. Boolean CoolN_Tree<Node,Type,nchild>::prev() {
  85.   Traversal_Type reverse_mode;
  86.   switch (this->t_mode) {
  87.   case INORDER:
  88.     reverse_mode = INORDER_REVERSE;
  89.     break;
  90.   case INORDER_REVERSE:
  91.     reverse_mode = INORDER;
  92.     break;
  93.   case PREORDER:
  94.     reverse_mode = PREORDER_REVERSE;
  95.     break;
  96.   case PREORDER_REVERSE:
  97.     reverse_mode = PREORDER;
  98.     break;
  99.   case POSTORDER:
  100.     reverse_mode = POSTORDER_REVERSE;
  101.     break;
  102.   case POSTORDER_REVERSE:
  103.     reverse_mode = POSTORDER;
  104.     break;
  105.   }
  106.   return this->next_internal (reverse_mode);
  107. }
  108.   
  109. // Get the next node in the tree based on the Traversal Type.  This
  110. // maintains a stack of parents in the tree for current position and
  111. // knows how to move forward and backward for preorder, inorder, or
  112. // postorder traversals. Changes here are most likely necessary in
  113. // Base_BT.C next_internal also.
  114.  
  115. template <class Node, class Type, int nchild>
  116. Boolean CoolN_Tree<Node,Type,nchild>::next_internal (Traversal_Type ttype) {
  117.   Node##_##Type##_##nchild##_p node, ptr1;
  118.   Node##_##Type##_##nchild##_p last_node = NULL;
  119.   CoolNT_Stack_Entry stack_entry;
  120.   int index;
  121.   Boolean forward = TRUE;
  122.  
  123.   switch (ttype) {
  124.   case INORDER_REVERSE:
  125.   case PREORDER_REVERSE:            // Are we going backward?
  126.   case POSTORDER_REVERSE:
  127.     forward = FALSE;
  128.     break;
  129.   }
  130.     
  131.   if (state.stack.is_empty()) {            // If stack is empty
  132.     node = this->root;                //  start with the root
  133.     if (forward)                //  init starting subtree
  134.       index = -1;                //    start at first subtree
  135.     else                    //    or
  136.       index = node->num_subtrees();        //    start at last subtree
  137.     state.stack.push (CoolNT_Stack_Entry ((long)node,index));
  138.     state.forward = forward;
  139.     
  140.   }
  141.   else {                    // Stack has some entries, so
  142.     stack_entry = state.stack.top();        //  get top entry from stack
  143.     node = (Node<Type,nchild>*)stack_entry.get_first();    //  load up node
  144.     index = (int)stack_entry.get_second();    //  and subtree index
  145.     last_node = node;                //  remember current position
  146.  
  147.     if (state.forward != forward) {        // Need to modify index
  148.       if (forward)                //  if we've changed direction.
  149.     index--;
  150.       else
  151.     index++;
  152.     }
  153.     state.forward = forward;            // Update direction.
  154.   }
  155.  
  156.   if (forward) {                // Going left to right
  157.     while (TRUE) {                // loop until next node found
  158.       if (++index < node->num_subtrees()) {    // incremented index in range?
  159.     if (node != last_node &&        // If we moved to new node &&
  160.         ((ttype == INORDER  && index == 1)  // Inorder after ltree or
  161.          ||(ttype == PREORDER && index == 0)// Preorder before ltree
  162.          ))
  163.       return TRUE;                // then this is next node
  164.  
  165.     state.stack.top().set_second(index);    // update stack with new index
  166.     ptr1 = node->sub_trees[index];        // get node's next subtree
  167.     if (ptr1) {                // When subtree exists
  168.       node = ptr1;                //   point node at subtree
  169.       index = -1;                //   init index for new node
  170.       state.stack.push (CoolNT_Stack_Entry ((long)node, index)); 
  171.     }
  172.       }
  173.       else {                    // No more subtrees for node
  174.     if (node != last_node &&        // If a new node
  175.         ttype == POSTORDER) {        //   and Postorder mode, 
  176.       return TRUE;                //   then this is next node
  177.     }
  178.     state.stack.pop();// pop this node from stack
  179.     if (state.stack.is_empty())            // Stack empty?
  180.       return FALSE;                //   indicate we're at the end
  181.         else {                    // Stack not empty, so
  182.       stack_entry = state.stack.top();    //  update stack_entry object
  183.       node = (Node<Type,nchild>*)stack_entry.get_first(); //  load up node
  184.       index = stack_entry.get_second();    //  and subtree index
  185.     }
  186.       }
  187.     }
  188.   }
  189.  
  190. // This is essesentially the same code as above, but going right to
  191. // left, giving reverse order capability
  192.   else {                                        // Going right to left
  193.     while (TRUE) {                // loop until next node found
  194.       if (--index > -1) {            // decremented index in range?
  195.     if (node != last_node &&        // If we moved to new node &&
  196.         ((ttype == INORDER_REVERSE &&    //  or Inorder_reverse node
  197.           index == 0)             //  is ready to do left subtree
  198.           || (ttype == POSTORDER_REVERSE &&    //  or Postorder_reverse is
  199.           index == (node->num_subtrees()-1))  // starting it's subtrees
  200.          ))
  201.       return TRUE;                // then this is next node
  202.     state.stack.top().set_second(index);    // update stack with new index
  203.     ptr1 = node->sub_trees[index];            // get node's next subtree
  204.     if (ptr1) {                // When subtree exists
  205.       node = ptr1;                //   point node at subtree
  206.       index = node->num_subtrees();        //   init index for new node
  207.       state.stack.push (CoolNT_Stack_Entry ((long)node, index)); 
  208.     }
  209.       }
  210.       else {                    // No more subtrees for node
  211.     if (node != last_node &&        // If a new node
  212.         ttype == PREORDER_REVERSE)             //   and Preorder_reverse
  213.       return TRUE;                //   this is next node
  214.  
  215.     state.stack.pop();            // pop this node from stack
  216.     if (state.stack.is_empty())        // Stack empty?
  217.       return FALSE;                //   indicate we're at the end
  218.         else {                    // Stack not empty, so
  219.       stack_entry = state.stack.top();    //  update stack_entry object
  220.       node = (Node<Type,nchild>*)stack_entry.get_first(); //  load up node
  221.       index = (int)stack_entry.get_second();    //  and subtree index
  222.     }
  223.       }
  224.     }
  225.   }
  226. }
  227.  
  228.  
  229. // value -- Return value of node at current position
  230. // Input: None
  231. // Output: Reference to value of node at current position
  232.  
  233. template <class Node, class Type, int nchild> 
  234. Type& CoolN_Tree<Node,Type,nchild>::value () { 
  235. #if ERROR_CHECKING 
  236.   if (this->state.stack.is_empty() )        // If no position established
  237.     this->value_error ();            // Raise exception
  238. #endif
  239.   CoolNT_Stack_Entry stack_entry = this->state.stack.top();
  240.   return (((Node<Type,nchild>*)stack_entry.get_first())->get());
  241. }
  242.  
  243.  
  244. // find -- Search the tree for a particular value. If found, update the current
  245. //         position marker.
  246. // Input:  Reference of value to search for
  247. // Output: TRUE/FALSE
  248.  
  249. template <class Node, class Type, int nchild> 
  250. Boolean CoolN_Tree<Node,Type,nchild>::find (const Type& value) {
  251.   for (this->reset (); this->next (); )     // For each node in tree
  252.     if (this->value() == value)            // If node found in tree
  253.       return TRUE;                // Inidicate success
  254.   return FALSE;                    // Inidicate failure
  255. }
  256.  
  257.  
  258. // preorder -- Perform a preorder traversal of tree by setting traversal mode,
  259. //             making node pointer cache, and applying function to each node
  260. // Input:      Pointer to function to apply to each node
  261. // Output:     None
  262.  
  263. template <class Node, class Type, int nchild> 
  264. void CoolN_Tree<Node,Type,nchild>::preorder (Node##_Apply_Function fn) {
  265.  
  266.   if (this->t_mode != PREORDER)         // If incorrect traversal mode
  267.     this->t_mode = PREORDER;            // Set preorder mode
  268.  
  269.   for (this->reset() ; this->next (); )        // For each preorder node
  270.     (*fn)(this->value());            // Apply function
  271. }
  272.  
  273.  
  274. // inorder -- Perform an inorder traversal of tree by setting traversal mode,
  275. //            making node pointer cache, and applying function to each node
  276. // Input:     Pointer to function to apply to each node
  277. // Output:    None
  278.  
  279. template <class Node, class Type, int nchild> 
  280. void CoolN_Tree<Node,Type,nchild>::inorder (Node##_Apply_Function fn) {
  281.   if (this->t_mode != INORDER)          // If incorrect traversal mode
  282.     this->t_mode = INORDER;            // Set inorder mode
  283.  
  284.   for (this->reset() ; this->next (); )        // For each preorder node
  285.     (*fn)(this->value());            // Apply function
  286. }
  287.  
  288.  
  289. // postorder -- Perform a postorder traversal of tree by setting traversal mode,
  290. //              making node pointer cache, and applying function to each node
  291. // Input:       Pointer to function to apply to each node
  292. // Output:      None
  293.  
  294. template <class Node, class Type, int nchild> 
  295. void CoolN_Tree<Node,Type,nchild>::postorder (Node##_Apply_Function fn) {
  296.   if (this->t_mode != POSTORDER)         // If incorrect traversal mode
  297.     this->t_mode = POSTORDER;            // Set postorder mode
  298.  
  299.   for (this->reset() ; this->next (); )        // For each preorder node
  300.     (*fn)(this->value());            // Apply function
  301. }
  302.  
  303. // current_position -- Get/Set iterator object for Tree
  304. // Input:              None
  305. // Output:             NT_State object of the Tree
  306.  
  307. template <class Node, class Type, int nchild>
  308. CoolNT_State& CoolN_Tree<Node,Type,nchild>::current_position () {
  309.   return this->state;
  310. }
  311.  
  312.  
  313. // do_count -- Perform an preorder traversal of N-ary tree to count nodes
  314. // Input:       Pointer to sub-tree node
  315. // Output:       None
  316.  
  317. template <class Node, class Type, int nchild>
  318. void CoolN_Tree<Node,Type,nchild>::do_count (Node<Type,nchild>* t) {
  319.   if (t != NULL) {                // If there is a subtree
  320.     this->number_nodes++;            // Increment node count
  321.     for (int i = 0; i < nchild; i++)        // For each pointer in vector
  322.       this->do_count (t->sub_trees[i]);        // Traverse each subtree
  323.   }
  324. }
  325.  
  326. // value_error -- Raise exception for CoolN_Tree::value()
  327. // Input:         None
  328. // Output:        None
  329.  
  330. template <class Node, class Type, int nchild> 
  331. void CoolN_Tree<Node,Type,nchild>::value_error () {
  332.   //RAISE Error, SYM(CoolN_Tree), SYM(Invalid_Cpos),
  333.   printf ("CoolN_Tree<%s,%s,%d>::value(): Invalid current position.\n",
  334.           #Type, #Node, nchild);
  335.   abort ();
  336. }
  337.